#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
  vector<vector<int>> threeSum(vector<int> &nums) {
    vector<vector<int>> res;
    // 小于3
    if (nums.size() < 3) {
      return res;
    }
    // 先排序
    sort(nums.begin(), nums.end(), less<int>());
    for (int i = 0; i < nums.size(); i++) {
      // 第一个元素大于零 结束循环
      if (nums[i] > 0) {
        return res;
      }
      // 除第一个元素外，其他元素与后面元素相等之间跳过
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }
      // 三数之和 sum = nums[i] + nums[l] + nums[r]
      int l = i + 1;
      int r = nums.size() - 1;
      while (l < r) {
        if (nums[i] + nums[l] + nums[r] == 0) {
          res.push_back({nums[i], nums[l], nums[r]});
          // 跳过重复元素
          while (l < nums.size() - 1 && nums[l] == nums[l + 1]) {
            l++;
          }
          while (r > l && nums[r] == nums[r - 1]) {
            r--;
          }
          // 判断下一组数据是否符合
          l++;
          r--;
        } else if (nums[i] + nums[l] + nums[r] > 0) {
          r--;
        } else {
          l++;
        }
      }
    }
    return res;
  }
};

int main() {
  vector<int> nums{-1, 0, 1, 2, -1, -4};
  Solution s;
  auto res = s.threeSum(nums);

  return 0;
}
